1. Field of the Invention
This invention relates to an arithmetic decoding method and device for decoding encoded image data formed by arithmetic coding, and more particularly to an arithmetic decoding method and device which are capable of processing not only bi-level (binary) images but also multi-level images, and a storage medium storing a program for executing the arithmetic decoding method.
2. Prior Art
In arithmetic coding, an interval on a number line [0, 1] where the square bracket on the interval end denotes equality being allowed and the curved bracket denotes it being disallowed is divided into sub-intervals according to probabilities of occurrence of symbols such that the sub-intervals have lengths corresponding to the probabilities of the symbols, respectively, and one of the sub-intervals corresponding to a symbol to be encoded is selected for encoding thereof. Then, the selected sub-interval is recursively subdivided into smaller sub-intervals according to the probabilities and one of the smaller sub-intervals corresponding to a symbol to be encoded next is selected for the encoding thereof. This recursive subdivision and selection of a sub-interval is repeatedly carried out for a whole sequence of symbols to be encoded, and coordinates of a point within a final sub-interval thus obtained is represented by a binary fraction which is at least distinguishable from those contained in the other sub-intervals so as to use the binary fraction as a code of the whole sequence of the symbols.
Typical arithmetic coding methods include the JBIG method (QM-coder) standardized by an organization called JBIG (Joint Bi-level Image Experts Group) which belongs to the ITU (International Telecommunications Union), and the Q-coder proposed by the IBM.
These methods use similar but different terminologies, and for the consistency of description of the present invention, in the following, the JBIG standard terminology will be used.
According to the basic theory of arithmetic coding, it is necessary for an arithmetic operation section of an encoder to carry out multiplications. This leads to a larger size of hardware of the arithmetic operation section and longer processing times for the multiplications. To eliminate these inconveniences, it is a mainstream method to use additions and subtractions in place of the multiplications, for simplified arithmetic operations.
The arithmetic operation section is comprised of an A register for holding the width or size (augend) of the current coding interval corresponding to an encoded sequence of symbols, and a code register (C register) for holding a value based on which an arithmetic code is generated. Assuming that a value corresponding to a probability that a more probable symbol (MPS) does not agree with a symbol to be encoded is defined as a probability estimate (LSZ), the arithmetic operation section is supplied with the more probable symbol (MPS), the value of the symbol to be encoded, and the LSZ, as input data, and carries out arithmetic operations (addition and subtraction) between the probability estimate LSZ and the values stored i the two registers, depending on information as to whether the symbol to be encoded agrees with the MPS, to thereby update the values of the two registers.
The aforementioned subinterval width is reduced whenever the recursive division is carried out, and hence the value of the A register is normalized to maintain accuracy of the coding. The normalization is performed by bit shifting of the A register and the C register to the left. Determined high-order bits of the C register are outputted as an arithmetic code.
When the encoded data is decoded, an arithmetic operation section of a decoder is supplied with an MPS, an LSZ, and an arithmetic code. Since it is possible to determine from the values of the LSZ and the arithmetic code whether or not the MPS and a symbol to be decoded agree with each other, the value of the symbol to be decoded can be calculated back.
The MPS and the LSZ are determined from information called a CX (context). The CX is comprised of nearby symbol values already generated when a symbol to be encoded is processed. In the JBIG method, a CX is composed of ten symbol values, which means that the CX can assume 1024 different values, and each CX having a different value has an MPS and a state value (ST) indicative of a probability. The LSZ is obtained by converting the state value of the CX with reference to a predetermined lookup table.
The MPS and ST of each context (CX) are updated under a specific condition, which makes it possible to learn a pattern peculiar to a sequence of symbols to be encoded, thereby enhancing decoding efficiency. More specifically, each pair of MPS and ST are set as data in a corresponding one of ten-bit addresses of a RAM (Random Access Memory) which are associated with possible values of the CX, and outputted from the RAM when the RAM is addressed by the CX. The MPS and ST in each address of the RAM are updated by rewriting the data thereof stored in the address.
In the arithmetic coding method, a symbol to be encoded and the MPS are binary, and hence the JBIG defines only the method for processing binary images. However, also in processing a multi-level image, it is possible to extract data on a bit-by-bit basis and subject the same to arithmetic operation. In this case, although the operation of the arithmetic operation section is not influenced by a difference between a binary image and a multi-level image, the manner of deriving the LSZ has to be considered deliberately, because the correlation in probability of occurrence between a symbol group (context) preceding a symbol to be encoded and the symbol to be encoded varies depending upon a bitplane to which the symbol to be encoded belongs. In short, a context paired with an LSZ is required to be set independently for each bitplane.
Another problem with the prior art is concerned with the speedup of decoding. From the principles of arithmetic coding, the closer the correlation between a context and a pixel being encoded, the higher the compression efficiency is. Further, pixels corresponding to the respective symbols of the context are required to have already been processed, so that e.g. in processing a 1-bit image, a symbol for a pixel immediately preceding the pixel being encoded is one of the components of the context. This imposes constraints on the speedup of processing for decoding by arithmetic operations, because the context cannot be identified until the value of the immediately preceding pixel is determined, and hence readout of the corresponding state value cannot be started.
As a solution to this problem, there has been proposed a method in which the RAM storing MPS's and ST's is divided into a plurality of RAM's so as to enable the possible state values to be read out beforehand. According to this solution, for example, when the value of the second preceding pixel is determined, the possibilities of the whole context are limited to two, one having a value of 0 for the immediately preceding pixel and the other having a value of 0 for the same, and therefore, at this time point, the data are simultaneously read from the two the RAM's, thereby allowing one of the two state values corresponding to the two context values to be selected at a time point the value of the immediately preceding pixel is determined.
In the above prior art, it is required to divide the memory in both of a case where the optimum arithmetic coding is carried out on a multi-level image and a case where high-speed decoding is carried out on a binary image. Further, even when an arithmetic decoding device capable of processing not only binary images but also multi-level images can have an arithmetic operation section commonly usable for processing the two kinds of images, memories for storing state values cannot be replaced by a common memory, which results in an increase in the manufacturing cost of the device.